package leetcode.code0310;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution2 implements IDebug {

	public List<Integer> findMinHeightTrees(int n, int[][] edges) {
		List<Integer> ans = new ArrayList<>();
		if (n == 1) {
			ans.add(0);
			return ans;
		}
		int[] ins = new int[n];
		HashSet<Integer>[] hash = new HashSet[n];
		for (int i = 0; i < n; i++) {
			hash[i] = new HashSet<>();
		}
		for (int[] edge : edges) {
			int ai = edge[0];
			int bi = edge[1];
			ins[ai] += 1;
			ins[bi] += 1;
			hash[ai].add(bi);
			hash[bi].add(ai);
		}
//		Queue<Integer> queue = new LinkedList<>();
		int[] queue = new int[n];
		int pq = 0;
		int[] queue1 = new int[n];
		int pq1 = 0;
		for (int i = 0; i < n; i++) {
			if (ins[i] == 1) {
//				queue.add(i);
				queue[pq++] = i;
			}
		}
		int left = n;
		while (left > 2) {
//			int size = queue.size();
			int size = pq;
			pq1 = 0;
			left -= size;
			while (size > 0) {
//				int cur = queue.poll();
				int cur = queue[--pq];
				size--;
				for (int edge : hash[cur]) {
					if (--ins[edge] == 1) {
						// queue.add(edge);
						queue1[pq1++] = edge;
					}
				}
			}
			queue = queue1;
			pq = pq1;
		}
//		while (!queue.isEmpty()) {
//			ans.add(queue.poll());
//		}
		while (pq > 0) {
			ans.add(queue[--pq]);
		}
		return ans;
	}

	@Override
	public void debug1() {
		List<Integer> e = HelpDebug.str2intlist("[3,4]");
		HelpDebug.compare(e, this.findMinHeightTrees(6, HelpDebug.str2array1("[[3,0],[3,1],[3,2],[3,4],[5,4]]")));
	}

	@Override
	public void debug2() {
		List<Integer> e = HelpDebug.str2intlist("[1]");
		HelpDebug.compare(e, this.findMinHeightTrees(4, HelpDebug.str2array1("[[1,0],[1,2],[1,3]]")));
	}

	@Override
	public void debug3() {
		List<Integer> e = HelpDebug.str2intlist("[0]");
		HelpDebug.compare(e, this.findMinHeightTrees(1, HelpDebug.str2array1("[]")));
	}

	@Override
	public void debug4() {
		List<Integer> e = HelpDebug.str2intlist("[0,1]");
		HelpDebug.compare(e, this.findMinHeightTrees(2, HelpDebug.str2array1("[[0,1]]")));
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
